1 Contenido de la clase
El modelo del árbol de decisiones [05:05-05:19, 08:35-08:51]
Se repasa que un algoritmo basado en comparaciones se puede representar como un árbol de decisiones: en cada nodo se hace una comparación y de cada nodo salen dos ramas según el resultado. El árbol se construye sobre elementos etiquetados (B, C, A, D). Las hojas son los resultados finales y los niveles (profundidades) se cuentan como 2, 3, 4 y 5 hacia abajo [08:35-08:51].
El número de hojas y las preguntas necesarias [23:23-25:28]
La capacidad de distinguir resultados depende del número de hojas: con 1 pregunta hay 2 hojas, con 2 hay 4, con 3 hay 8 ("ha sido la 1, tengo 2; ha sido la 2, tengo 4; ha sido la 3, tengo 8"). Para ordenar hay que distinguir 3! = 6 permutaciones; con 2 preguntas solo se llega a 4 hojas, por lo que no alcanza y hacen falta al menos 3 comparaciones [25:12-25:28]. En general, el número de hojas es 2^H con H preguntas: H=1 → 2, H=2 → 4, H=3 → 8, H=4 → 16 [40:30-40:58].
Límite inferior de la ordenación [26:30-29:53]
Para cualquier algoritmo basado en comparaciones, la altura H del árbol en el mejor caso no es del orden de N, sino de log₂(n!); no se puede bajar de ese valor [29:31-29:53]. Con el ejemplo de los enteros del 1 al 8 se muestra cómo ir determinando el orden comparando de a pares ("uno con dos, era más chica") [44:24-44:41].
El problema del mínimo: n−1 comparaciones [42:51-46:53]
Se pasa a un problema más sencillo: encontrar el mínimo. La estrategia es comparar desde el inicio, ir quedándose con el elemento más pequeño y guardar su posición [43:16-43:58]. Cada comparación elimina al menos un candidato, por lo que el costo es de n−1 comparaciones en el peor caso [46:25-46:53]. Este es un límite inferior informativo: vale para cualquier implementación basada solo en comparaciones.
Selección frente a ordenación [29:31-29:53, 66:49-66:59]
Se compara el costo de los dos problemas: ordenar cuesta del orden de log₂(n!) ≈ n log n, mientras que seleccionar el mínimo cuesta n−1. Ordenar da más información de la necesaria si solo se quiere el mínimo, por eso seleccionar es más barato. Con el método del torneo y su historia de comparaciones se puede obtener también el segundo y tercer mínimo revisando a los elementos que perdieron directamente contra el ganador [47:55-48:11, 66:49-66:59].
Caso peor frente a caso mejor [29:31-29:53]
El análisis distingue entre el caso peor (altura máxima del árbol, todas las comparaciones del camino más largo) y el caso mejor. En un árbol con L hojas, la altura es al menos ⌈log₂ L⌉; para el mínimo L = n, pero el algoritmo concreto necesita n−1 comparaciones en el camino peor [29:31-29:53]. [parte no entendida — detalle del desarrollo en la pizarra].
2 Puntos destacados / Lo que hay que saber
3 Actividades y tareas pendientes
En esta clase no se dejó ninguna tarea concreta con fecha de entrega. Conviene practicar por cuenta propia:
4 Dudas que podrían examinar
¿Por qué encontrar el mínimo cuesta exactamente n−1 comparaciones?
Porque cada comparación elimina al menos un candidato; con n candidatos y uno solo ganador hacen falta n−1 [46:25-46:53].
¿Se pueden obtener el mínimo y el segundo mínimo con menos comparaciones?
Sí, con el método del torneo se recupera el segundo mínimo revisando a los que perdieron directamente contra el ganador, en lugar de comparar todo de nuevo [47:55-48:11].
¿Cuál es el límite inferior para el k-ésimo elemento más pequeño?
Del orden de n + min(k, n−k) + Θ(log n); el mínimo (k = 1) es el caso más barato con n−1.
¿Cómo se relacionan las hojas con las comparaciones?
Un árbol con L hojas tiene altura al menos ⌈log₂ L⌉; para ordenar L = n!, y para el mínimo L = n [24:01-25:16].
¿Por qué el modelo de comparaciones es restrictivo?
Solo las comparaciones binarias dan información de orden; algoritmos que usan estructuras de datos, distribuciones o información adicional pueden romper el límite.
¿Ordenar es siempre necesario para elegir el mínimo?
No; seleccionar cuesta n−1 mientras que ordenar cuesta del orden de n log n [29:31-29:53].
5 Sitios o recursos para visitar
El profesor no citó libros, páginas ni herramientas concretas en esta clase. Recursos útiles para profundizar lo explicado:
Árboles de decisión y por qué ordenar cuesta al menos log₂(n!). · google.com
Demostración del límite inferior log₂(n!) de la ordenación. · geeksforgeeks.org
Encontrar el mínimo y el segundo mínimo con la historia del torneo. · google.com
Curso completo de introducción a algoritmos. · ocw.mit.edu
Capítulo de ordenación y selección del libro de referencia clásico. · google.com
Visualizaciones interactivas de algoritmos de ordenación y selección. · visualgo.net
6 Glosario de términos
- Algoritmo basado en comparaciones: algoritmo cuyo comportamiento depende solo de comparaciones binarias entre los elementos.
- Árbol de decisiones: modelo de un algoritmo de comparaciones; cada nodo es una comparación y cada hoja un resultado.
- Hoja: resultado final de un camino del árbol de decisiones.
- Altura del árbol (H): el número máximo de comparaciones a lo largo de un camino.
- Límite inferior: cota mínima de costo que todo algoritmo debe cumplir, independiente de la implementación.
- Selección: problema de encontrar un elemento por su orden (p. ej. el mínimo); cuesta n−1 comparaciones.
- Mínimo: el elemento más pequeño de una lista; cada comparación elimina al menos un candidato.
- Historia del torneo: registro de las comparaciones de un torneo; permite recuperar el segundo y tercer mínimo.
- Caso peor: la situación en que el algoritmo hace el máximo número de operaciones (la altura máxima del árbol).
- Caso mejor: la situación en que el algoritmo hace el mínimo número de operaciones.
7 Mapa mental textual
- Diseño y Análisis de Algoritmos · Clase 4
- Árbol de decisiones
- Nodos = comparaciones, hojas = resultados
- Con H preguntas → 2^H hojas
- Altura con L hojas ≥ ⌈log₂ L⌉
- Ordenación por comparaciones
- Necesita n! hojas (permutaciones)
- n = 3 → 3! = 6 hojas → 3 comparaciones
- Altura = log₂(n!), no N
- Selección del mínimo
- Comparar desde el inicio, guardar el más pequeño y su posición
- Costo: n−1 comparaciones (cada una elimina un candidato)
- Límite informativo, independiente de la implementación
- Selección vs ordenación
- Seleccionar: n−1
- Ordenar: n log n
- Torneo + historia → segundo y tercer mínimo
- Caso peor vs caso mejor
- Altura máxima (peor) frente a la mínima (mejor)
- Árbol de decisiones